#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
https://leetcode.cn/problems/4sum/

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        sort(nums.begin(), nums.end());
        // for (int x : nums) cout << x << ' ';

        int n = nums.size();
        vector<vector<int>> ret;
        int left, right;
        long long sum = 0;

        for (int i = 0; i < n - 3; )
        {
            for (int j = i + 1; j < n - 2; )
            {
                left = j + 1;
                right = n - 1;
                sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                while (left < right)
                {

                    if (sum > target)
                    {
                        sum -= nums[right];
                        // do { --right; } while (left < right && nums[right] == nums[right+1]);
                        --right;
                        sum += nums[right];
                    }
                    else if (sum < target)
                    {
                        sum -= nums[left];
                        // do { ++left; } while (left < right && nums[left] == nums[left-1]);
                        ++left;
                        sum += nums[left];
                    }
                    else
                    {
                        ret.push_back({ nums[i], nums[j], nums[left], nums[right] });
                        sum -= nums[left];
                        do { ++left; } while (left < right && nums[left] == nums[left - 1]);
                        sum += nums[left];
                        sum -= nums[right];
                        do { --right; } while (left < right && nums[right] == nums[right + 1]);
                        sum += nums[right];
                    }
                }

                do { ++j; } while (j < n - 2 && nums[j] == nums[j - 1]);
            }

            do { ++i; } while (i < n - 3 && nums[i] == nums[i - 1]);
        }

        return ret;
    }
};